package org.leetcode.middle.leetcode215;

public class Solution {

    public int findKthLargest(int[] nums, int k) {

        QuickSort3Ways(nums,0,nums.length-1);

        return nums[nums.length-k];

    }

    //三路快排 https://zhuanlan.zhihu.com/p/357002752
    private static void QuickSort3Ways(int [] arr ,int left, int right){

        if (left>=right){
            return;
        }

        //基准值
        int v = arr[left];

        //小于v区间的右边界
        int lt = left;
        //大于v区间的左边界
        int gt = right+1;

        //遍历的下标
        int i = left+1;

        while (i<gt){

            if (arr[i]<v){
                swap(arr,i,lt+1);
                i++;
                lt++;
            }else if (arr[i]>v){
                swap(arr,i,gt-1);
                gt--;
            }else {
                i++;
            }
        }
        //将基准值与小于v区间的右边界的值进行交换
        swap(arr,left,lt);

        QuickSort3Ways(arr,left,lt-1);
        QuickSort3Ways(arr,gt,right);

    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    //超时
    public void quickSort(int [] nums,int left ,int right){
        if (left>right){
            return;
        }

        int pv = nums[left];
        int i = left;
        int j = right;
        int temp;

        while (i<j){
            //先判断右边
            while (i<j && pv<nums[j]){
                j--;
            }
            //再判断左边
            while (i<j && pv>=nums[i]){
                i++;
            }

            //交换左右两个的数
            if (i<j){
                temp=nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
            }

        }

        //将i和j相遇的数与pv进行交换
        nums[left]=nums[i];
        nums[i]=pv;

        quickSort(nums,left,i-1);
        quickSort(nums,i+1,right);

    }

    public static void main(String[] args) {
        int [] nums = {3,2,3,1,2,4,5,5,6};

        Solution solution = new Solution();

        int num = solution.findKthLargest(nums, 4);

        System.out.println(num);
    }


}
